The invention relates generally to a method for routing data packets through a packet communication network and more specifically to a method for routing data packets in a network where the best paths between nodes are stored in a routing table generated at each node.
Packet communication is a form of data communication whereby segments or packets of data are routed with error checking and confirmation of receipt. Packets may be transmitted directly between a source node and a destination node or may be relayed via a number of relay nodes. Several methods of data packet routing are known.
One method is known as directory-based routing. According to this method the address in the header of a packet is used as an index to a directory of packet routing lists stored in a source node. A packet routing list consists of an ordered list of packet node identifiers or call signs that represent a complete transmission path from the source node to the destination node. Once the packet is sent from the source node, its path through the network is determined by the packet routing list that was stored in the source node. Packet routing lists must be prepared with knowledge about the connectivity of each node in the network, and in a typical directory-based routing scheme, each node must maintain a complete routing list for every other node in the network to which it sends packets. Directory-based routing schemes require continued maintenance and communication of network interconnection information employed in the directory. Each of these functions drains network resources and this can severely reduce performance in a large network. However, directory-based routing techniques have the advantage of permitting optimization of routing for a wide variety of network parameters, including data delay, throughput, reliability, priority and the like.
Another basic family of routing techniques are the non-directory-based routing techniques. In non-directory-based routing, the complexities associated with directory-based routing techniques are avoided. There is no need to store connectivity information for each transmitting node in the network, thus reducing the amount of overhead processing that must be done by the network to preserve network connections. However, non-directory-based routing techniques generally do not permit network parameter optimization.
In U.S. Pat. No. 4,939,726, issued to Baran, et al., and assigned to the assignee of the present invention, a non-directory-based routing method and system that permit network parameter optimization are disclosed. According to the method described therein, each node in a network is uniquely identified by absolute geographical coordinates or by a code indicating absolute location in an external coordinate-based reference system (node coordinates), and such absolute geographical coordinates or the equivalent are employed as part of a packet identifier for each packet. A means at each node through which a packet is routed uses the packet destination coordinates and the node coordinates of its neighboring nodes to determine a desired forwarding route of a data packet. A routing decision is made for each packet that is received, even if that packet is directed to a destination for which the node has already received a packet. The routing may be prioritized according to preselected criteria, preferably achieving optimum forward progress, that is, maximum forward progress using the least amount of power and taking into account characteristics of the system.
Accordingly, the Baran packet routing method uses no routing directory or table to perform data routing. Each node of the network collects or is otherwise provided with information about the quality of communication between itself and the neighboring nodes within the node's communication range. When a data packet has been received at a node, the data packet is routed further through the network based on criteria derived from the history of communication between the local node and its neighbors. The criteria include distance, power requirements, retry history (reliability), throughput history, speed of transfer (net data rate), network delay, and data priority. Typically, there is an initialization procedure which is executed to determine the latitude and longitude of neighbors within a destination quadrant, and the criteria are weighted in accordance with preselected preferences to establish, at each subject node, a link quality (LQ) factor for each possible destination local to the subject node. For each packet received and needing to be forwarded, a node in the Baran system creates a list of possible relay nodes, orders that list, and then polls the neighboring nodes to see which node is available.
While the system disclosed in Baran has been shown to perform well and with advantages over directory-based routing schemes, there is a cost and delay in the Baran network due to each node in the network having to make a routing decision about each packet it receives. What is needed is a network and a routing method that preserves the advantages of the Baran coordinate-based addressing scheme but that does not require the overhead and processing of every packet that is required in the Baran system to make a routing decision about each packet.